#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string>
#include<cstring> 
#include<iostream>
#include<vector> 
#include<stack>
using namespace std;

#define ROW 21
#define COLUMN 16
const int COUNT = ROW * COLUMN;
static int global_num = 0;
static int lexCount = 0;

struct KeyWords {
	string sign;
	string de
	int number;
};

struct item {
	item(string s, int t) { name = s; type = t; }
	string name;
	int type;
};

FILE* in1, * in2, * in3, * out;
string code[105];
int table[ROW][COLUMN];
char corres[COLUMN] = "+-*/%(){};><= ";
string m_map[11] = { "S","B","C","E","E1","A","T","T1","M","F","L" };
vector<string>yans;
stack<item>st;
 
int parsetable[11][17] = {
	{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,0,-1},
	{-1,2,-1,-1,-1,2,-1,-1,-1,-1,-1,-1,-1,2,2,-1,-1},
	{-1,-1,-1,-1,-1,-1,-1,3,4,5,6,7,8,-1,-1,-1,-1},
	{-1,9,-1,-1,-1,9,-1,-1,-1,-1,-1,-1,-1,9,9,-1,-1},
	{10,10,-1,-1,-1,-1,11,11,11,11,11,11,11,-1,-1,-1,11},
	{12,13,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
	{-1,14,-1,-1,-1,14,-1,-1,-1,-1,-1,-1,-1,14,14,-1,-1},
	{16,16,15,15,15,-1,16,16,16,16,16,16,16,-1,-1,-1,16},
	{-1,-1,17,18,19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
	{-1,21,-1,-1,-1,20,-1,-1,-1,-1,-1,-1,-1,22,23,-1,-1},
	{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,24,-1,-1},
};

KeyWords keywords[10] = {
	{"int","int",0},
	{"char","char",1},
	{"float","float",2},
	{"if","if",3},
	{"while","while",4},
	{"then","then",5},
	{"else","else",6}
};

KeyWords rules[50];
KeyWords ans[505];


int pow(int a, int b)
{
	int num = 1;
	while (b--)
	{
		num *= a;
	}
	return num;
}

int readTableFile(const char *infile)
{
	if ((in1 = fopen(infile, "r")) == NULL)
	{
		printf("cannot open infile!\n");
		return 0;
	}

	int cnt = 0;
	while (1)
	{
		char tmpIn = fgetc(in1);
		int val = 0;
		while (tmpIn != ' ' && tmpIn != '\n' && tmpIn!=EOF)
		{
			val = val * 10 + (int)tmpIn - '0';
			tmpIn = fgetc(in1);
		}
		int row = cnt / COLUMN;
		int column = cnt % COLUMN;
		table[row][column] = val;
		if (tmpIn == EOF) break;
		cnt++;
	}
}

int judge(char ch)
{
	if ((ch >= 'a' && ch <= 'z') || (ch >= 'A') && (ch <= 'Z')) return 0;
	else if (ch >= '0' && ch <= '9') return 1;
	else {
		for (int i = 0; i < COLUMN; i++) {
			if (ch == corres[i]) return i + 2;
		}
		return -1;
	}
}

int readRules(const char *infile)
{
	if ((in2 = fopen(infile, "r")) == NULL)
	{
		printf("cannot open infile!\n");
		return 0;
	}
	int cnt = 0;
	while (1)
	{
		char tmpIn1 = fgetc(in2);
		if (tmpIn1 == EOF) break;
		while (tmpIn1 != ' ') {
			rules[cnt].sign += tmpIn1;
			tmpIn1 = fgetc(in2);
		}
		tmpIn1 = fgetc(in2);
		while (tmpIn1 != ' ') {
			rules[cnt].desp += tmpIn1;
			tmpIn1 = fgetc(in2);
		}
		rules[cnt].number = (int)fgetc(in2) - '0';
		if (fgetc(in2) == EOF) break;
		cnt++;
	}

}

int readCode(const char *filename)
{
	if ((in3 = fopen(filename, "r")) == NULL)
	{
		printf("cannot open infile!\n");
		return 0;
	}

	int count = 0; //��������������

	//ѭ����ȡÿһ�У�ֱ���ļ�β
	while (1)
	{
		char tmpIn = fgetc(in3);
		if (tmpIn == '\n')
		{
			count++;
			continue;
		}
		if (tmpIn == EOF) break;
		code[count] += tmpIn;
	}
	return count + 1;
}


void show(int state, string str)
{
	rules[state-1].sign = str;
	if (state == 1)
	{
		rules[state - 1].number = global_num++;
		for (int i = 0; i < 10; i++)
		{
			if (str == keywords[i].sign)
			{
				ans[lexCount++] = keywords[i];
				return;
			}
		}
	}
	if (state == 2)
	{
		rules[state - 1].number = stoi(str);
	}
	//cout << "(" << rules[state-1].sign << "," << rules[state-1].desp << "," << rules[state-1].number << ")" << endl;
	ans[lexCount++] = rules[state - 1];
}

int analyse(string str)
{
	int state = 0;
	string tmpStr = "";
	for (int i = 0; i < str.size(); i++) {
		char tmp = str[i];
		int tmpState = state;
		int curr_ch = judge(tmp);
		if (curr_ch == -1)
		{
			return -1;
		}
		state = table[state][curr_ch];
		//cout << state << " " << tmp << " " << curr_ch << endl;
		
		if (state == 0)
		{
			i--;
			show(tmpState, tmpStr);
			tmpStr = "";
		}
		
		if (curr_ch == 15) { i++; continue; }
		if (state != 0) tmpStr += tmp;
		if (i == str.size() - 1) show(state, tmpStr);
	}
	return 1;
}

int getNumber(KeyWords k)
{
	if (k.desp == "NUM") return 13;
	if (k.desp == "ID") return 14;
	if (k.desp == "OP") return k.number;
	if (k.desp == "RELOP") return k.number + 7;
	if (k.sign == "(") return 5;
	if (k.sign == ")") return 6;
	if (k.desp == "if") return 15;
	if (k.sign == "end") return 16;
	return -1;
}

int letterMap(item temp)
{
	for (int i = 0; i < 11; i++)
		if (temp.name == m_map[i])
			return i;
	return -1;
}

int action(int choice)
{
	switch (choice)
	{
	case 0: {
		yans.push_back("S -> IF(B)S");
		st.pop();
		st.push(item("S", 1));
		st.push(item(")", 0));
		st.push(item("B", 1));
		st.push(item("(", 0));
		st.push(item("if", 0));
		break;
	}
	case 1:
		yans.push_back("S -> L=E");
		st.pop();
		st.push(item("E", 1));
		st.push(item("=", 0));
		st.push(item("L", 1));
		break;
	case 2:
		yans.push_back("S -> EC");
		st.pop();
		st.push(item("C", 1));
		st.push(item("E", 1));
		break;
	case 3:
		yans.push_back("C -> <E");
		st.pop();
		st.push(item("E", 1));
		st.push(item("<", 0));
		break;
	case 4:
		yans.push_back("C -> >E");
		st.pop();
		st.push(item("E", 1));
		st.push(item(">", 0));
		break;
	case 5:
		yans.push_back("C -> <=E");
		st.pop();
		st.push(item("E", 1));
		st.push(item("<=", 0));
		break;
	case 6:
		yans.push_back("C -> >=E");
		st.pop();
		st.push(item("E", 1));
		st.push(item(">=", 0));
		break;
	case 7:
		yans.push_back("C -> ==E");
		st.pop();
		st.push(item("E", 1));
		st.push(item("==", 0));
		break;
	case 8:
		yans.push_back("C -> <>E");
		st.pop();
		st.push(item("E", 1));
		st.push(item("<>", 0));
		break;
	case 9:
		yans.push_back("E -> TE1");
		st.pop();
		st.push(item("E1", 1));
		st.push(item("T", 1));
		break;
	case 10:
		yans.push_back("E1 -> AE1");
		st.pop();
		st.push(item("E1", 1));
		st.push(item("A", 1));
		break;
	case 11:
		yans.push_back("E1 -> #");
		st.pop();
		break;
	case 12:
		yans.push_back("A -> +T");
		st.pop();
		st.push(item("T", 1));
		st.push(item("+", 0));
		break;
	case 13:
		yans.push_back("A -> -T");
		st.pop();
		st.push(item("T", 1));
		st.push(item("-", 0));
		break;
	case 14:
		yans.push_back("T -> FT1");
		st.pop();
		st.push(item("T1", 1));
		st.push(item("F", 1));
		break;
	case 15:
		yans.push_back("T1 -> MT1");
		st.pop();
		st.push(item("T1", 1));
		st.push(item("M", 1));
		break;
	case 16:
		yans.push_back("T1 -> #");
		st.pop();
		break;
	case 17:
		yans.push_back("M -> *F");
		st.pop();
		st.push(item("F", 1));
		st.push(item("*", 0));
		break;
	case 18:
		yans.push_back("M -> /F");
		st.pop();
		st.push(item("F", 1));
		st.push(item("/", 0));
		break;
	case 19:
		yans.push_back("M -> %F");
		st.pop();
		st.push(item("F", 1));
		st.push(item("%", 0));
		break;
	case 20:
		yans.push_back("F -> (E)");
		st.pop();
		st.push(item(")", 0));
		st.push(item("E", 1));
		st.push(item("(", 0));
		break;
	case 21:
		yans.push_back("F -> -F");
		st.pop();
		st.push(item("F", 1));
		st.push(item("-", 1));
		break;
	case 22:
		yans.push_back("F -> NUM");
		st.pop();
		st.push(item("NUM", 0));
		break;
	case 23:
		yans.push_back("F -> L");
		st.pop();
		st.push(item("L", 1));
		break;
	case 24:
		yans.push_back("L -> ID");
		st.pop();
		st.push(item("ID", 0));
		break;

	default:
		return -1;
	}
	return 1;
}

int main()
{
	readTableFile("table.txt");
	readRules("rule.txt");
	out = fopen("out.txt", "w");

	int state = 0;
	int count = readCode("test.txt");
	for (int i = 0; i < count; i++)
	{
		int success = analyse(code[i]);
		if (success == -1)
		{
			cout << "Row " << i + 1 << "lexical error!" << endl;
			break;
		}
		ans[lexCount++] = KeyWords({ "end","end",0 });
	}

	for (int i = 0; i < lexCount; i++)
	{
		cout << "(" << ans[i].sign << "," << ans[i].desp << "," << ans[i].number << ")" << endl;
	}
	cout << endl;

	int d = 0;
	int ycnt = 0;
	st.push(item("S", 1));

	while ((!st.empty())||(d<lexCount-1))
	{
		if (st.empty()) { ycnt++; d++; st.push(item("S", 1)); }
		KeyWords k = ans[d];
		int number = getNumber(k);
		item temp = st.top();
		if (temp.type == 0)
		{
			if (temp.name == k.desp || temp.name == k.sign)
			{
				st.pop();
				d++;
			}
			else
			{
				cout << "Row " << ycnt + 1 << " grammatical error!" << endl;
				fprintf(out, "%s %d %s\n", "Row",ycnt + 1,"grammatical error!");
				break;
			}
		}
		else
		{
			int mapNumber = letterMap(temp);
			int next = parsetable[mapNumber][number];
			//cout << mapNumber << " " << number << " "<<next << endl;
			int flag = action(next);
			if (flag == -1)
			{
				cout << "Row " << ycnt + 1 << "grammatical error!" << endl;
				fprintf(out, "%s %d %s\n", "Row", ycnt + 1, "grammatical error!");
				break;
			}
		}
	}
		
	for (int i = 0; i < yans.size(); i++)
	{
		cout << yans[i] << endl;
	}

	for (int i = 0; i < yans.size(); i++)
	{
		fprintf(out, "%s\n", yans[i].c_str());
	}
}
